package com.sheng.leetcode.year2024.month04.day18;

import org.junit.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author by ls
 * @date 2024/4/18
 * <p>
 * 2007. 从双倍数组中还原原数组<p>
 * <p>
 * 一个整数数组 original 可以转变成一个 双倍 数组 changed ，转变方式为将 original 中每个元素 值乘以 2 加入数组中，然后将所有元素 随机打乱 。<p>
 * 给你一个数组 changed ，如果 change 是 双倍 数组，那么请你返回 original数组，否则请返回空数组。original 的元素可以以 任意 顺序返回。<p>
 * <p>
 * 示例 1：<p>
 * 输入：changed = [1,3,4,2,6,8]<p>
 * 输出：[1,3,4]<p>
 * 解释：一个可能的 original 数组为 [1,3,4] :<p>
 * - 将 1 乘以 2 ，得到 1 * 2 = 2 。<p>
 * - 将 3 乘以 2 ，得到 3 * 2 = 6 。<p>
 * - 将 4 乘以 2 ，得到 4 * 2 = 8 。<p>
 * 其他可能的原数组方案为 [4,3,1] 或者 [3,1,4] 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：changed = [6,3,0,1]<p>
 * 输出：[]<p>
 * 解释：changed 不是一个双倍数组。<p>
 * <p>
 * 示例 3：<p>
 * 输入：changed = [1]<p>
 * 输出：[]<p>
 * 解释：changed 不是一个双倍数组。<p>
 * <p>
 * 提示：<p>
 * 1 <= changed.length <= 10^5<p>
 * 0 <= changed[i] <= 10^5<p>
 */
public class LeetCode2007 {

    @Test
    public void test01() {
//        int[] changed = {1, 3, 4, 2, 6, 8};
//        int[] changed = {6, 3, 0, 1};
        int[] changed = {1};
        System.out.println(Arrays.toString(new Solution().findOriginalArray(changed)));
    }
}

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int length = changed.length;
        if (length % 2 != 0) return new int[0];
        Arrays.sort(changed);
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : changed) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        int[] original = new int[length / 2];
        int i = 0;
        for (int num : changed) {
            if (map.getOrDefault(num, 0) == 0) {
                continue;
            }
            map.put(num, map.getOrDefault(num, 0) - 1);
            if (map.getOrDefault(num * 2, 0) == 0) {
                return new int[0];
            }
            map.put(num * 2, map.getOrDefault(num * 2, 0) - 1);
            original[i++] = num;
        }
        return original;
    }
}
